package Linklist;

/**
 * @Classname JZ22链表中倒数第k个节点
 * @Description TODO
 * @Date 2023/2/9 22:01
 * @Created by xjl
 */
public class JZ22链表中倒数第k个节点 {

    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    // 删除倒数的k个节点 使用链表的翻转 然后在使用
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode rehead=reverse(head);
        ListNode curr=rehead;
        while (k!=0&&curr!=null){
            curr=curr.next;
            --k;
        }
        curr.next=null;
        return reverse(rehead);
    }

    public ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode curr=head;
        while (curr!=null){
            ListNode next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }

    // 统计所有的个数 然后在遍历这个之前的那个
    public ListNode getKthFromEnd2(ListNode head, int k) {
        int count=0;
        ListNode curr=head;
        while (curr!=null){
            count++;
            curr=curr.next;
        }
        int index=count-k-1;
        // 防止kc超过了count的值，那倒数的就是这个链表
        if (k>=count){
            return head;
        }
        while (index!=0){
            head=head.next;
            index--;
        }
        ListNode res=head.next;
        return res;
    }
}
